public class Text6 {
    // 有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.
    // 问最多能装入背包的总价值是多大?
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int num = A.length;
        if(m == 0 || num == 0)
            return 0;

        // 前i个物品放入大小为j的背包中所获得的最大价值
        int[][] maxValue = new int[num + 1][m + 1];

        for(int i = 0; i <= num; ++i){
            maxValue[i][0] = 0;
        }

        for(int i = 1; i <= m; ++i){
            maxValue[0][i] = 0;
        }

        for(int i = 1; i <= num; ++i){
            for(int j = 1; j <= m; ++j){
                if(A[i - 1] > j) {
                    maxValue[i][j] = maxValue[i - 1][j];
                } else {
                    int newValue = maxValue[i - 1][j - A[i - 1]] + V[i - 1];
                    maxValue[i][j] = Math.max(newValue, maxValue[i - 1][j]);
                }
            }
        }

        return maxValue[num][m];
    }
}
